class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        vector<int> prefix_sum(len, nums[0]);
        for (int i = 1; i < len; i++)   //计算前缀和
            prefix_sum[i] = prefix_sum[i - 1] + nums[i];

        int ret = 0;
        unordered_map<int, int> hash;   //key_val:前缀和及其出现的次数
        hash[0]++;  //考虑到前缀和直接等于k的情况
        for (int i = 0; i < len; i++)
        {
            int tmp = prefix_sum[i] - k;
            if (hash.count(tmp))
                ret += hash[tmp]; 

            hash[prefix_sum[i]]++;
        }

        return ret;
    }
};